package LC;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC22
 * @Description: TODO
 * @Author hl
 * @Date 2021/3/30
 * @Version V1.0
 **/
public class LC22 {

    public static void main(String[] args) {
        List<String> res= generateParenthesis(3);
        System.out.println(res.toString());
    }

    public static List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        generateWords("",n,n,res);
        return res;

    }

    public static void generateWords(String s, int left, int right, List<String> res) {
       if(left==0&&right==0){
           res.add(s);
           return;
       }
       if(left==right){   //剩余左右括号数相等，下一个只能用左括号
           generateWords(s+"(",left-1,right,res);
       }else{
           if(left<right){//剩余左括号小于右括号，下一个可以用左括号也可以用右括号
               if(left>0){
                   generateWords(s+"(",left-1,right,res);
               }
               generateWords(s+")",left,right-1,res);
           }//没有else 因为右括号数量大于左括号数量，那就证明已经不符合题意了

       }
    }
}
